//动态规划
/**
 * 股票买卖
 * 状态转移方程：dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i]) // sell
 *            dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i]) // buy
 *            base case: dp[-i][k][0] = dp[i][0][0] = 0;
 *                       dp[-1][k][1] = dp[i][0][1] = -infinity;
 */

 // k=1 : leetcode 121
 /**
  * dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][1][1] + prices[i])
  * dp[i][1][1] = max(dp[i-1][1][1], - prices[i]);
  * 去掉k的影响：
  * dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
  * dp[i][1] = max(dp[i-1][1], - prices[i]);
  * 代码表示：
  * for(let i=0;i<n;i++){
  *    if(i == 0){
  *       dp[i][0] = 0;
  *       dp[i][1] = -prices[i];
  *    }
  *    dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
  *    dp[i][1] = max(dp[i-1][1], - prices[i]);
  * }
  * return dp[n-1][0]
  * 发现新状态只和相邻的状态有关，可以压缩状态空间复杂度至O(1)：
  */
 var maxProfit = function(prices) {
     let n = prices.length;
     let dp_i0 = 0,dp_i1 = Number.MIN_SAFE_INTEGER;
     for(let i=0;i<n;i++){
         dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
         dp_i1 = Math.max(dp_i1, -prices[i]);
     }
     return dp_i0;
};

//k=+infinity; leetcode 122
/**
 * k为正无穷则 k = k-1;
 * dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
 * dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i])
 * 
 */
var maxProfitInfinity = function(prices) {
    let n = prices.length;
    let dp_i0 = 0,dp_i1 = Number.MIN_SAFE_INTEGER;
    for(let i=0;i<n;i++){
        let temp = dp_i0;
        dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
        dp_i1 = Math.max(dp_i1, temp - prices[i]);
    }
    return dp_i0;
};

// k=+infinity + cooldown; leetcode 309
/**  每次sell后要等一天才能继续交易
 * dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
 * dp[i][1] = max(dp[i-1][1],dp[i-2][0] - prices[i]) //i-1变为i-2
 */
var maxProfit = function(prices) {
    let n = prices.length;
    let dp_i0 = 0,dp_i1 = Number.MIN_SAFE_INTEGER;
    let dp_pre0 = 0;
    for(let i=0;i<n;i++){
        let temp = dp_i0;
        dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
        dp_i1 = Math.max(dp_i1, dp_pre0 - prices[i]);
        dp_pre0 = temp;
        
    }
    return dp_i0;
};
// k=+infinity + fee; leetcode 714
/** 参考k 正无穷的情况并且减去fee
 * dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
 * dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i] - fee) //减去fee
 */
var maxProfit = function(prices, fee) {
    let n = prices.length;
    let dp_i0 = 0,dp_i1 = Number.MIN_SAFE_INTEGER;
    for(let i=0;i<n;i++){
        let temp = dp_i0;
        dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
        dp_i1 = Math.max(dp_i1, temp - prices[i]) - fee;
    }
    return dp_i0;
};

// k=2; leetcode 123
/**
 * 穷举k的情况 for循环for(let i=1;i<=k;i++)
 * 本题k较小 手动把k=1  k=2的情况写出来
 */
var maxProfit = function(prices) {
    let n = prices.length;
    let dp_i10 = 0,dp_i11 = Number.MIN_SAFE_INTEGER;
    let dp_i20 = 0,dp_i21 = Number.MIN_SAFE_INTEGER;
    for(let i=0;i<n;i++){
        dp_i20 = Math.max(dp_i20, dp_i21+prices[i]);
        dp_i21 = Math.max(dp_i21, dp_i10 - prices[i]);

        dp_i10 = Math.max(dp_i10,dp_i11 + prices[i]);
        dp_i11 = Math.max(dp_i11, -prices[i]);
    }
    return dp_i20;
};

// k=any integer; leetcode 188
/**
 * 需要分情况穷举k:
 * 一次交易由买入和卖出构成，至少需要两天，
 * 所以说有效的限制次数 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。
 */
var maxProfit = function(k, prices) {
    let n = prices.length;
    if( k > n/2) {
        return maxProfitInfinity(prices);
    }
    let dp = Array.from(new Array(n),()=>new Array(k+1));
    for(let i=0;i<n;i++){
        for(let r = 0;r<=k;r++){
            dp[i][r] = new Array(2).fill(0);
        }
    }
    for(let i=0;i<n;i++){
        for(let j=k;j>=1;j--){
            if(i == 0){
                dp[i][j][0] = 0;
                dp[i][j][1] = -prices[i];
                continue;
            }
            dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
            dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
        }
    }
    return dp[n-1][k][0]
};

//打家劫舍1： leetcode 198
var rob = function(nums) {
    let n = nums.length;
    let dp = new Array(n+2).fill(0);
    for(let i=n-1;i>=0;i--){
        dp[i] = Math.max(dp[i+1],dp[i+2] + nums[i]);
    }
    return dp[0];
};
//状态压缩
var rob = function(nums) {
    let n = nums.length;
    let dp_i1=dp_i2=0;
    let dp_i = 0;
    for(let i=n-1;i>=0;i--){
        dp_i = Math.max(dp_i1,dp_i2+nums[i]);
        dp_i2 = dp_i1;
        dp_i1 = dp_i;
    }
    return dp_i;
};
//打家劫舍2： leetcode 213
var rob = function(nums) {
   let n = nums.length;
   if(n === 1) return nums[0];
   const robRange = (nums,start,end)=>{
       let dp_i1=dp_i2=0;
       let dp_i = 0;
       for(let i=end;i>=start;i--){
            dp_i = Math.max(dp_i1,dp_i2+nums[i]);
            dp_i2 = dp_i1;
            dp_i1 = dp_i;
       }
       return dp_i;
   }
   return Math.max(robRange(nums,0,n-2),robRange(nums,1,n-1))
};
//打家劫舍3:二叉树 leetcode 337
var rob = function(root) {
    const dp = (root) =>{
        if(root == null){
            return [0,0];
        }
        let left = dp(root.left);
        let right = dp(root.right);
        let rob = root.val + left[0] + right[0];
        let not_rob = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        return [not_rob,rob];
    }
    let res = dp(root);
    return Math.max(res[0],res[1]);
};

//子序列问题：
/**
 * 编辑距离：72
 */
var minDistance = function(word1, word2) {
    let m = word1.length,n = word2.length;
    let dp = Array.from(new Array(m+1),()=>new Array(n+1).fill(0));
    for(let i=1;i<=m;i++){
       dp[i][0] = i;
    }
    for(let j=1;j<=n;j++){
        dp[0][j] = j;
    }
    for(let i=1;i<=m;i++){
        for(let j=1;j<=n;j++){
            if(word1[i-1] == word2[j-1]){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = Math.min(
                    dp[i-1][j] + 1,
                    dp[i][j-1] + 1,
                    dp[i-1][j-1] + 1
                )
            }
        }
    }
    return dp[m][n];
};